package 图.有向图;

import 抽象数据类型.Digraph;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-05
 */
public class 找出强连通分量Kosaraju算法 {
    public class KosarajuSCC{
        private boolean[] marked;//已访问过的顶点
        private int[] id ;//强连通分量
        private int count;//强连通分量的数量
        public KosarajuSCC(Digraph g){
            marked = new boolean[g.V()];
            id = new int[g.V()];
            基于深度优先搜索的顶点排序.DepthFirstOrder order = new 基于深度优先搜索的顶点排序.DepthFirstOrder(g.reverse());
            for (Integer s : order.reversePost()) {
                if (!marked[s]) {
                    dfs(g,s);
                    count++;
                }
            }
        }

        private void dfs(Digraph g, Integer v) {
            marked[v] = true;
            id[v] = count;
            for (Integer w : g.adj(v)) {
                if (!marked[w]) {
                    dfs(g, w);
                }
            }
        }

        public boolean stronglyConnected(int v, int w) {
            return id[w] == id[v];
        }

        public int id(int v) {
            return id[v];
        }

        public int count() {
            return count;
        }

    }
}
